package 数据结构.树;

import java.util.ArrayList;

/**
 * @author Zhu
 * @Description
 * @create 2023-02-27
 */
public class JZ68二叉搜索树的最近公共祖先 {
    //递归
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        if(root == null)
            return -1;
        if((p >= root.val && q<=root.val) || (p<=root.val && q>=root.val))
            return root.val;
        else if(p<=root.val && q<=root.val)
            return lowestCommonAncestor(root.left,p,q);
        else
            return lowestCommonAncestor(root.right,p,q);
    }

    //搜索路径比较 非递归
    public ArrayList<Integer> getPath(TreeNode root, int target) {
        ArrayList<Integer> path = new ArrayList<>();
        TreeNode node = root;
        while (node.val!=target){
            path.add(node.val);
            if(target<node.val)
                node = node.left;
            else
                node=node.right;
        }
        path.add(node.val);
        return path;
    }

    public int lowestCommonAncestor2 (TreeNode root, int p, int q) {
        ArrayList<Integer> pathp = getPath(root, p);
        ArrayList<Integer> pathq = getPath(root, q);
        int res = 0;
        for(int i=0;i<pathp.size() && i<pathq.size();i++){
            int x =pathp.get(i);
            int y = pathq.get(i);
            if(x==y)
                res = pathp.get(i);
            else
                break;
        }
        return res;
    }
}
